{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Employee Free Time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: employeeFreeTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #员工空闲时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定员工的 <code>schedule</code> 列表，表示每个员工的工作时间。</p>\n",
    "\n",
    "<p>每个员工都有一个非重叠的时间段&nbsp; <code>Intervals</code> 列表，这些时间段已经排好序。</p>\n",
    "\n",
    "<p>返回表示 <em>所有 </em>员工的 <strong>共同，正数长度的空闲时间 </strong>的有限时间段的列表，同样需要排好序。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]\n",
    "<strong>输出：</strong>[[3,4]]\n",
    "<strong>解释：</strong>\n",
    "共有 3 个员工，并且所有共同的\n",
    "空间时间段是 [-inf, 1], [3, 4], [10, inf]。\n",
    "我们去除所有包含 inf 的时间段，因为它们不是有限的时间段。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]\n",
    "<strong>输出：</strong>[[5,6],[7,9]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>（尽管我们用 <code>[x, y]</code> 的形式表示 <code>Intervals</code> ，内部的对象是 <code>Intervals</code> 而不是列表或数组。例如，<code>schedule[0][0].start = 1, schedule[0][0].end = 2</code>，并且 <code>schedule[0][0][0]</code>&nbsp;是未定义的）</p>\n",
    "\n",
    "<p>而且，答案中不包含 [5, 5] ，因为长度为 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>schedule</code> 和&nbsp;<code>schedule[i]</code>&nbsp;为长度范围在&nbsp;<code>[1, 50]</code>的列表。</li>\n",
    "\t<li><code>0 &lt;= schedule[i].start &lt; schedule[i].end &lt;= 10^8</code>。</li>\n",
    "</ol>\n",
    "\n",
    "<p><strong>注：</strong>输入类型于&nbsp;2019 年&nbsp;4 月 15 日 改变。请重置为默认代码的定义以获取新方法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [employee-free-time](https://leetcode.cn/problems/employee-free-time/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [employee-free-time](https://leetcode.cn/problems/employee-free-time/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[[1,2],[5,6]],[[1,3]],[[4,10]]]', '[[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        pq = [[availability[0].start, i, 0] for i, availability in enumerate(schedule)]\n",
    "        heapq.heapify(pq)\n",
    "        common_free_time = []\n",
    "        anchor = None\n",
    "        while pq:\n",
    "            curr_start, employ_id, time_id = heapq.heappop(pq)\n",
    "            if anchor and curr_start > anchor:\n",
    "                common_free_time.append(Interval(anchor, curr_start))\n",
    "            anchor = max(anchor, schedule[employ_id][time_id].end) if anchor else schedule[employ_id][time_id].end\n",
    "            if time_id + 1 < len(schedule[employ_id]):\n",
    "                heapq.heappush(pq, [schedule[employ_id][time_id + 1].start, employ_id, time_id + 1])\n",
    "        return common_free_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # we use priority queue to solve this\n",
    "        # we order we order start time / endtime for all empoloyees, we use i, j to indicate its associate with the i-th empolyee and the j-th checked interval\n",
    "        # we maintain the latested end time marker, and check with every employee's start time\n",
    "        # if start time is bigger, than the universal end time, there's a gap and we register, we go over all queues to find all possible intervals\n",
    "        # the reason this should work is because we always consider the earliest time for all emploees, so the gap is always hold and there will be no interference between\n",
    "\n",
    "        q = []\n",
    "        \n",
    "\n",
    "        # q = [(emp[0].start, i, 0) for i, emp in enumerate(schedule)]\n",
    "        heapify(q)\n",
    "        universalend = 1000000\n",
    "        for i, emp in enumerate(schedule):\n",
    "            start, end = emp[0].start, emp[0].end\n",
    "            heappush(q, (start, i, 0))\n",
    "            universalend = min(universalend, start)\n",
    "        # universalend = min(emp[0].start for emp in schedule)\n",
    "        # universalend = min(interval.start for emp in schedule for interval in emp)\n",
    "        res = []\n",
    "\n",
    "        while q:\n",
    "            cur_start, cur_emp, cur_i = heappop(q)\n",
    "\n",
    "            if universalend < cur_start:\n",
    "                res.append(Interval(universalend, cur_start))\n",
    "            \n",
    "            universalend = max(universalend, schedule[cur_emp][cur_i].end)\n",
    "\n",
    "\n",
    "            if cur_i < len(schedule[cur_emp]) - 1: # not the last\n",
    "                # add the nexst (including the last)\n",
    "\n",
    "                heappush(q, (schedule[cur_emp][cur_i+1].start, cur_emp, cur_i+1))\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # set q, this is actually priority queue, but in python it's also heapq\n",
    "        q = [(emp[0].start, i, 0) for i, emp in enumerate(schedule)] # go through all emps and register start time, the i-th empoly, the x-th position of the work interval, for the initialiization, we consider only the first interval for all emps.\n",
    "        heapify(q)\n",
    "\n",
    "        out = []\n",
    "        # specify cur_check time, initially it's the minimum start time for all, which is treated as the last finished \n",
    "        cur_check = min(interval.start for emp in schedule for interval in emp)\n",
    "\n",
    "        while q: # the queue will maintain all emps' intervals from their corresponding first to last\n",
    "            cur_start, cur_i_emp, cur_i_interval = heappop(q)\n",
    "            if cur_check < cur_start: # meaning the currently checked start time is before the last registerd finished, so we find a common interval\n",
    "                out.append(Interval(cur_check, cur_start))\n",
    "            \n",
    "            # increase the cur_check by the current interval as this current interval will end at that time regarless of the above if condition, so meaning at leaset one emp is working between cur_check and the end of the cur emp\n",
    "            cur_check = max(cur_check, schedule[cur_i_emp][cur_i_interval].end)\n",
    "\n",
    "            # after checking this emp's cur interval, we append it to the queue (priority queue will maiteina order based on the first element in the tuple, in this case is the interval start time. This is to guarantee we do not miss a conmmon free interval because the above condition alwasy compare the cur_check with the values of the start point)\n",
    "            # load on queue\n",
    "            if cur_i_interval < len(schedule[cur_i_emp])-1: # not the last interval for the emp\n",
    "                heappush(q, (schedule[cur_i_emp][cur_i_interval+1].start, cur_i_emp, cur_i_interval+1))\n",
    "\n",
    "        return out\n",
    "\n",
    "\n",
    "    \n",
    "        # ans = []\n",
    "        # pq = [(emp[0].start, ei, 0) for ei, emp in enumerate(schedule)]\n",
    "        # heapq.heapify(pq)\n",
    "        # anchor = min(iv.start for emp in schedule for iv in emp)\n",
    "        # while pq:\n",
    "        #     t, e_id, e_jx = heapq.heappop(pq)\n",
    "        #     if anchor < t:\n",
    "        #         ans.append(Interval(anchor, t))\n",
    "        #     anchor = max(anchor, schedule[e_id][e_jx].end)\n",
    "        #     if e_jx + 1 < len(schedule[e_id]):\n",
    "        #         heapq.heappush(pq, (schedule[e_id][e_jx+1].start, e_id, e_jx+1))\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\n",
    "    # def __str__(self):\n",
    "    #     return f\"[{self.start}, {self.end}]\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        \n",
    "        # Combine all intervals into a single list\n",
    "        all_intervals = []\n",
    "        for emp_schedule in schedule:\n",
    "            all_intervals.extend(emp_schedule)\n",
    "\n",
    "        # Sort intervals by their start times\n",
    "        all_intervals.sort(key=lambda x: x.start)\n",
    "\n",
    "        # Identify free time intervals\n",
    "        res = []\n",
    "        end_time = all_intervals[0].end\n",
    "        for i in range(1, len(all_intervals)):\n",
    "            # If there's a gap between the end of the last interval and the start of the current one\n",
    "            if all_intervals[i].start > end_time:\n",
    "                res.append(Interval(end_time, all_intervals[i].start))\n",
    "            # Update the end_time to be the max of the current interval's end or the existing end_time\n",
    "            end_time = max(end_time, all_intervals[i].end)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\n",
    "    def __str__(self):\n",
    "        return f\"[{self.start}, {self.end}]\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        \n",
    "        # Combine all intervals into a single list\n",
    "        all_intervals = []\n",
    "        for emp_schedule in schedule:\n",
    "            all_intervals.extend(emp_schedule)\n",
    "\n",
    "        # Sort intervals by their start times\n",
    "        all_intervals.sort(key=lambda x: x.start)\n",
    "\n",
    "        # Identify free time intervals\n",
    "        res = []\n",
    "        end_time = all_intervals[0].end\n",
    "        for i in range(1, len(all_intervals)):\n",
    "            # If there's a gap between the end of the last interval and the start of the current one\n",
    "            if all_intervals[i].start > end_time:\n",
    "                res.append(Interval(end_time, all_intervals[i].start))\n",
    "            # Update the end_time to be the max of the current interval's end or the existing end_time\n",
    "            end_time = max(end_time, all_intervals[i].end)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        res = []\n",
    "        pq = [(emp[0].start, i, 0) for i, emp in enumerate(schedule)]\n",
    "        heapq.heapify(pq)\n",
    "        lastest_end = pq[0][0]\n",
    "\n",
    "        while pq:\n",
    "            earliest_start, i, job_i = heapq.heappop(pq)\n",
    "            if lastest_end < earliest_start:\n",
    "                res.append(Interval(lastest_end, earliest_start))\n",
    "\n",
    "            lastest_end = max(lastest_end, schedule[i][job_i].end)\n",
    "\n",
    "            if job_i < len(schedule[i]) - 1:\n",
    "                heapq.heappush(pq, (schedule[i][job_i + 1].start, i, job_i + 1))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        \"\"\"\n",
    "        [1,2] [1,3] [4,10] [5,6]\n",
    "        [1,3] [4,10]\n",
    "        [1,3] [2,4] [2,5] [6,7] [9,12]\n",
    "        [1,5] [6,7] [9,12]\n",
    "        \"\"\"\n",
    "        nums = []\n",
    "        for x in schedule:\n",
    "            for val in x:\n",
    "                nums.append([val.start, val.end])\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        for x, y in nums:\n",
    "            if len(res) == 0 or res[-1][1] < x:\n",
    "                res.append([x, y])\n",
    "            else:\n",
    "                res[-1][1] = max(res[-1][1], y)\n",
    "        ans = []\n",
    "        for i in range(1, len(res)):\n",
    "            ans.append(Interval(res[i - 1][1], res[i][0]))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        temp = []\n",
    "        for s in schedule:\n",
    "            temp.extend(s)\n",
    "        temp.sort(key = lambda x: x.start)\n",
    "        right = temp[0].end\n",
    "        res = []\n",
    "        for i in range(1, len(temp)):\n",
    "            if temp[i].start > right:\n",
    "                res.append(Interval(start=right, end=temp[i].start))\n",
    "            right = max(right, temp[i].end)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "            events,ans = [],[]\n",
    "            for emp in schedule:\n",
    "                for iv in emp:\n",
    "                    events.append((iv.start, -1))\n",
    "                    events.append((iv.end, 1))\n",
    "            events.sort()\n",
    "            prev,bal = None,0\n",
    "            for t,v in events:\n",
    "                if prev and bal == 0:\n",
    "                    ans.append(Interval(prev, t))\n",
    "                bal -= v\n",
    "                prev = t\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        # intervals = []\n",
    "        # for x in schedule:\n",
    "        #     for y in x:\n",
    "        #         intervals.append([y.start,y.end])\n",
    "        # intervals.sort()\n",
    "        # #print(intervals)\n",
    "        # a = []\n",
    "        # s,e = intervals[0]\n",
    "        # for x,y in intervals[1:]:\n",
    "        #     if x > e:\n",
    "        #         a.append([s,e])\n",
    "        #         s,e = x,y\n",
    "        #     else:\n",
    "        #         e = max(e,y)\n",
    "        # a.append([s,e])\n",
    "        # # print(a)\n",
    "\n",
    "        # ans = []\n",
    "        # for i,[x,y] in enumerate(a):\n",
    "        #     if i > 0:\n",
    "        #         ans.append((a[i - 1][1],x))\n",
    "        # return [Interval(x,y) for x,y in ans]\n",
    "\n",
    "        \"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        intervals = sorted([i for s in schedule for i in s], key=lambda x: x.start)\n",
    "        ans = []\n",
    "        end = intervals[0].end\n",
    "        for i in intervals[1:]:\n",
    "            if i.start > end:\n",
    "                ans.append(Interval(end, i.start))\n",
    "            end = max(end, i.end)\n",
    "        \n",
    "        return ans\n",
    "        # print(intervals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        \n",
    "        OPEN, CLOSE = 0, 1\n",
    "\n",
    "        events=[]\n",
    "        for em in schedule:\n",
    "            for iv in em:\n",
    "                events.append((iv.start,OPEN))\n",
    "                events.append((iv.end,CLOSE))\n",
    "        events.sort()\n",
    "        ret=[]\n",
    "        score,pre=0,-1\n",
    "        \n",
    "        for t,mark in events:\n",
    "            if score==0 and pre != -1:\n",
    "                ret.append(Interval(pre,t))\n",
    "            score+=1 if mark is OPEN else -1\n",
    "            pre=t\n",
    "        return ret\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # set q, this is actually priority queue, but in python it's also heapq\n",
    "        q = [(emp[0].start, i, 0) for i, emp in enumerate(schedule)] # go through all emps and register start time, the i-th empoly, the x-th position of the work interval, for the initialiization, we consider only the first interval for all emps.\n",
    "        heapify(q)\n",
    "\n",
    "        out = []\n",
    "        # specify cur_check time, initially it's the minimum start time for all\n",
    "        cur_check = min(interval.start for emp in schedule for interval in emp)\n",
    "\n",
    "        while q: # the queue will maintain all emps' intervals from their corresponding first to last\n",
    "            cur_start, cur_i_emp, cur_i_interval = heappop(q)\n",
    "            if cur_check < cur_start: # meaning the currently checked start time is before the last registerd finished, so we find a common interval\n",
    "                out.append(Interval(cur_check, cur_start))\n",
    "            \n",
    "            # increase the cur_check by the current interval as this current interval will end at that time regarless of the above if condition, so meaning at leaset one emp is working between cur_check and the end of the cur emp\n",
    "            cur_check = max(cur_check, schedule[cur_i_emp][cur_i_interval].end)\n",
    "\n",
    "            # after checking this emp's cur interval, we append it to the queue (priority queue will maiteina order based on the first element in the tuple, in this case is the interval start time. This is to guarantee we do not miss a conmmon free interval because the above condition alwasy compare the cur_check with the values of the start point)\n",
    "            # load on queue\n",
    "            if cur_i_interval < len(schedule[cur_i_emp])-1: # not the last interval for the emp\n",
    "                heappush(q, (schedule[cur_i_emp][cur_i_interval+1].start, cur_i_emp, cur_i_interval+1))\n",
    "\n",
    "        return out\n",
    "\n",
    "\n",
    "    \n",
    "        # ans = []\n",
    "        # pq = [(emp[0].start, ei, 0) for ei, emp in enumerate(schedule)]\n",
    "        # heapq.heapify(pq)\n",
    "        # anchor = min(iv.start for emp in schedule for iv in emp)\n",
    "        # while pq:\n",
    "        #     t, e_id, e_jx = heapq.heappop(pq)\n",
    "        #     if anchor < t:\n",
    "        #         ans.append(Interval(anchor, t))\n",
    "        #     anchor = max(anchor, schedule[e_id][e_jx].end)\n",
    "        #     if e_jx + 1 < len(schedule[e_id]):\n",
    "        #         heapq.heappush(pq, (schedule[e_id][e_jx+1].start, e_id, e_jx+1))\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        # 1 2 3 4 5 6 7 8 9 10\n",
    "        # - - \n",
    "        # - \n",
    "        #        ----------\n",
    "        #        -  \n",
    "        res = []\n",
    "        arr = []\n",
    "        for sche in schedule:\n",
    "            for inter in sche:\n",
    "                s = inter.start\n",
    "                e = inter.end\n",
    "                arr.append([s, e])\n",
    "                \n",
    "        arr.sort()\n",
    "        pre = arr[0][1]\n",
    "        for s, e in arr:\n",
    "            if pre < s:\n",
    "                res.append(Interval(pre, s))\n",
    "            pre = max(pre, e)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        pq = []\n",
    "        for i in range(len(schedule)):\n",
    "            pq.append([schedule[i][0].start, schedule[i][0].end, i, 0])\n",
    "        heapify(pq)\n",
    "\n",
    "        tmp = []\n",
    "        while pq:\n",
    "            start, end, i, j = heappop(pq)\n",
    "            if tmp and tmp[-1][1] >= start:\n",
    "                tmp[-1][1] = max(tmp[-1][1], end)\n",
    "            else:\n",
    "                tmp.append([start, end])\n",
    "\n",
    "            if j + 1 < len(schedule[i]):\n",
    "                heappush(pq, [schedule[i][j + 1].start, schedule[i][j + 1].end, i, j + 1])\n",
    "        \n",
    "        res = []\n",
    "        prev_end = tmp[0][1]\n",
    "        for start, end in tmp[1:]:\n",
    "            res.append(Interval(prev_end, start))\n",
    "            prev_end = end\n",
    "\n",
    "        return res\n",
    "\n",
    "                 \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "\n",
    "        \n",
    "        #maintian the lastend, if last compared to the current start has a gap, this is what we want\n",
    "\n",
    "\n",
    "\n",
    "        res = []\n",
    "\n",
    "\n",
    "        q = []\n",
    "        heapify(q)\n",
    "\n",
    "        last_end = 1000000\n",
    "        for i, item in enumerate(schedule):\n",
    "            heappush(q, (item[0].start, i, 0)) # i-th emp j=0-th interval\n",
    "            last_end = min(last_end, item[0].start)\n",
    "\n",
    "        print(q)\n",
    "        while q:\n",
    "            cur_start, cur_i, cur_pos = heappop(q)\n",
    "\n",
    "            if cur_start > last_end:\n",
    "                res.append(Interval(last_end, cur_start))\n",
    "            \n",
    "            last_end = max(last_end, schedule[cur_i][cur_pos].end)\n",
    "\n",
    "            if cur_pos < len(schedule[cur_i]) - 1: # not the last\n",
    "                heappush(q, (schedule[cur_i][cur_pos+1].start, cur_i, cur_pos+1))\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # we use priority queue to solve this\n",
    "        # we order we order start time / endtime for all empoloyees, we use i, j to indicate its associate with the i-th empolyee and the j-th checked interval\n",
    "        # we maintain the latested end time marker, and check with every employee's start time\n",
    "        # if start time is bigger, than the universal end time, there's a gap and we register, we go over all queues to find all possible intervals\n",
    "        # the reason this should work is because we always consider the earliest time for all emploees, so the gap is always hold and there will be no interference between\n",
    "\n",
    "        q = []\n",
    "        \n",
    "\n",
    "        # q = [(emp[0].start, i, 0) for i, emp in enumerate(schedule)]\n",
    "        heapify(q)\n",
    "        universalend = 1000000\n",
    "        for i, emp in enumerate(schedule):\n",
    "            start, end = emp[0].start, emp[0].end\n",
    "            heappush(q, (start, i, 0))\n",
    "            universalend = min(universalend, start)\n",
    "        # universalend = min(emp[0].start for emp in schedule)\n",
    "        # universalend = min(interval.start for emp in schedule for interval in emp)\n",
    "        res = []\n",
    "\n",
    "        while q:\n",
    "            cur_start, cur_emp, cur_i = heappop(q)\n",
    "\n",
    "            if universalend < cur_start:\n",
    "                res.append(Interval(universalend, cur_start))\n",
    "            \n",
    "            universalend = max(universalend, schedule[cur_emp][cur_i].end)\n",
    "\n",
    "\n",
    "            if cur_i < len(schedule[cur_emp]) - 1: # not the last\n",
    "                # add the nexst (including the last)\n",
    "\n",
    "                heappush(q, (schedule[cur_emp][cur_i+1].start, cur_emp, cur_i+1))\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # set q, this is actually priority queue, but in python it's also heapq\n",
    "        q = [(emp[0].start, i, 0) for i, emp in enumerate(schedule)] # go through all emps and register start time, the i-th empoly, the x-th position of the work interval, for the initialiization, we consider only the first interval for all emps.\n",
    "        heapify(q)\n",
    "\n",
    "        out = []\n",
    "        # specify cur_check time, initially it's the minimum start time for all, which is treated as the last finished \n",
    "        cur_check = min(interval.start for emp in schedule for interval in emp)\n",
    "\n",
    "        while q: # the queue will maintain all emps' intervals from their corresponding first to last\n",
    "            cur_start, cur_i_emp, cur_i_interval = heappop(q)\n",
    "            if cur_check < cur_start: # meaning the currently checked start time is before the last registerd finished, so we find a common interval\n",
    "                out.append(Interval(cur_check, cur_start))\n",
    "            \n",
    "            # increase the cur_check by the current interval as this current interval will end at that time regarless of the above if condition, so meaning at leaset one emp is working between cur_check and the end of the cur emp\n",
    "            cur_check = max(cur_check, schedule[cur_i_emp][cur_i_interval].end)\n",
    "\n",
    "            # after checking this emp's cur interval, we append it to the queue (priority queue will maiteina order based on the first element in the tuple, in this case is the interval start time. This is to guarantee we do not miss a conmmon free interval because the above condition alwasy compare the cur_check with the values of the start point)\n",
    "            # load on queue\n",
    "            if cur_i_interval < len(schedule[cur_i_emp])-1: # not the last interval for the emp\n",
    "                heappush(q, (schedule[cur_i_emp][cur_i_interval+1].start, cur_i_emp, cur_i_interval+1))\n",
    "\n",
    "        return out\n",
    "\n",
    "\n",
    "    \n",
    "        # ans = []\n",
    "        # pq = [(emp[0].start, ei, 0) for ei, emp in enumerate(schedule)]\n",
    "        # heapq.heapify(pq)\n",
    "        # anchor = min(iv.start for emp in schedule for iv in emp)\n",
    "        # while pq:\n",
    "        #     t, e_id, e_jx = heapq.heappop(pq)\n",
    "        #     if anchor < t:\n",
    "        #         ans.append(Interval(anchor, t))\n",
    "        #     anchor = max(anchor, schedule[e_id][e_jx].end)\n",
    "        #     if e_jx + 1 < len(schedule[e_id]):\n",
    "        #         heapq.heappush(pq, (schedule[e_id][e_jx+1].start, e_id, e_jx+1))\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "        times = []\n",
    "        for sche in schedule:\n",
    "            for interval in sche:\n",
    "                times.append((interval.start, 0))\n",
    "                times.append((interval.end, 1))\n",
    "\n",
    "        def cmp(x,y):\n",
    "            if x[0] == y[0]:\n",
    "                return 1 if x[1] == 1 else -1\n",
    "            return x[0] - y[0]\n",
    "        \n",
    "        times.sort(key=cmp_to_key(cmp))\n",
    "\n",
    "        # print(times)\n",
    "        res = []\n",
    "        cnt = 0\n",
    "        free = None\n",
    "        for t in times:\n",
    "            if t[1] == 0:\n",
    "                cnt += 1\n",
    "                if res and res[-1].end == -1:\n",
    "                    res[-1].end = t[0]\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    res.append(Interval(t[0], -1))\n",
    "    \n",
    "        return res[:-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        oc = []\n",
    "        for ent in schedule:\n",
    "            for sch in ent:\n",
    "                oc.append((sch.start, 1))\n",
    "                oc.append((sch.end, 0))\n",
    "        oc.sort()\n",
    "        last = -1\n",
    "        res = []\n",
    "        cnt = 0\n",
    "        for ev in oc:\n",
    "            if ev[1]:\n",
    "                if not cnt and ev[0] - last:\n",
    "                    res.append(Interval(last, ev[0]))\n",
    "                cnt += 1\n",
    "            else:\n",
    "                last = ev[0]\n",
    "                cnt -= 1\n",
    "        return res[1: ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        Interval.__lt__ = lambda x, y: x.start < y.start\n",
    "        ans = []\n",
    "        heap = []\n",
    "        for emp in schedule:\n",
    "            heap.extend(emp)\n",
    "        heapify(heap)\n",
    "        lst = []\n",
    "        while len(heap) > 0:\n",
    "            interval = heappop(heap)\n",
    "            if not lst or interval.start > lst[-1].end:\n",
    "                lst.append(interval)\n",
    "            else:\n",
    "                lst[-1].end = max(lst[-1].end, interval.end)\n",
    "        end = lst[0].end\n",
    "        for i in range(1, len(lst)):\n",
    "            cur = lst[i]\n",
    "            if cur.start > end:\n",
    "                ans.append(Interval(end, cur.start))\n",
    "            end = cur.end\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        rec = []\n",
    "        for sche in schedule:\n",
    "            for inter in sche:\n",
    "                rec.append([inter.start,inter.end])\n",
    "\n",
    "        rec.sort()\n",
    "        pre = rec[0][1]\n",
    "        ans = []\n",
    "        for start,end in rec:\n",
    "            if start > pre:\n",
    "                ans.append(Interval(pre,start))\n",
    "            pre = max(pre,end)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        intervals=[]\n",
    "        for a in schedule:\n",
    "            for b in a:\n",
    "                intervals.append([b.start,b.end])\n",
    "        intervals.sort()\n",
    "        #区间合并\n",
    "        n=len(intervals)\n",
    "        res=[intervals[0]]\n",
    "        for i in range(1,n):\n",
    "            if intervals[i][0]>=res[-1][1]:\n",
    "                res.append(intervals[i])\n",
    "            else:\n",
    "                res[-1][1]=max(res[-1][1],intervals[i][1])\n",
    "        ans=[]\n",
    "        for i in range(1,len(res)):\n",
    "            if res[i-1][1]<res[i][0]:\n",
    "                ans.append(Interval(res[i-1][1],res[i][0]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        \n",
    "        list_of_intervals = []\n",
    "        for emloyee_time in schedule:\n",
    "            list_of_intervals.extend(emloyee_time)\n",
    "        \n",
    "        list_of_intervals.sort(key=lambda x:x.start)\n",
    "\n",
    "        res = []\n",
    "        end = list_of_intervals[0].end \n",
    "        for i in range(1, len(list_of_intervals)):\n",
    "            if list_of_intervals[i].start > end:\n",
    "                res.append(Interval( end,  list_of_intervals[i].start))\n",
    "            end = max(end, list_of_intervals[i].end)\n",
    "\n",
    "        res.sort(key=lambda x:x.start)\n",
    "        return res\n",
    "        \n",
    "        # 需要初始化一个res = []\n",
    "        # 先把所有的interval放进一个list里面，然后对这个list of object根据start time进行排序\n",
    "        # 排序完之后，我们先设置第一个object的end time为我们需要的end\n",
    "        # 遍历这个list of interval，从第二个interval，即 i = 0 开始遍历\n",
    "                 # 寻找一个 interval.start > 当前end，如果存在，我们就把这个结果存入res（注意存入的时候，我们又要把它变回一个Interval object）\n",
    "        # 最后返回这个res\n",
    "        # 时间 nlogn，因为使用到了排序； n表示所有的空闲时间数量。 空间 O（n）\n",
    "                     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        intervals = []\n",
    "        for s in schedule:\n",
    "            for inter in s:\n",
    "                intervals.append([inter.start, inter.end])\n",
    "        intervals.sort()\n",
    "\n",
    "        ans = []\n",
    "        preEnd = intervals[0][1]\n",
    "        for curStart, curEnd in intervals[1:]:\n",
    "            if preEnd < curStart:\n",
    "                ans.append(Interval(preEnd, curStart))\n",
    "            preEnd = max(preEnd, curEnd)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        OPEN, CLOSE = 0, 1\n",
    "\n",
    "        events=[]\n",
    "        for em in schedule:\n",
    "            for iv in em:\n",
    "                events.append((iv.start,OPEN))\n",
    "                events.append((iv.end,CLOSE))\n",
    "        events.sort()\n",
    "        ret=[]\n",
    "        score,pre=0,-1\n",
    "        \n",
    "        for t,mark in events:\n",
    "            if score==0 and pre != -1:\n",
    "                ret.append(Interval(pre,t))\n",
    "            score+=1 if mark is OPEN else -1\n",
    "            pre=t\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        START, END = 0, 1\n",
    "        events = []\n",
    "        for emp in schedule:\n",
    "            for interval in emp:\n",
    "                events.append((interval.start, START))\n",
    "                events.append((interval.end, END))\n",
    "        events.sort()\n",
    "        ans = []\n",
    "        pre = -inf\n",
    "        balance = 0\n",
    "        for t, cmd in events:\n",
    "            if balance == 0 and pre != -inf:\n",
    "                ans.append(Interval(pre, t))\n",
    "            balance += 1 if cmd == START else -1\n",
    "            pre = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        rec = []\n",
    "        for sche in schedule:\n",
    "            for inter in sche:\n",
    "                s = inter.start\n",
    "                e = inter.end\n",
    "                rec.append([s,e])\n",
    "        rec.sort()\n",
    "        head = rec[0][0]\n",
    "        tail = rec[0][1]\n",
    "        res= []\n",
    "        for  x,y in rec[1:]:\n",
    "            if x<=tail:\n",
    "                tail = max(y,tail)\n",
    "            else:\n",
    "                res.append(Interval(tail,x))\n",
    "                head = x\n",
    "                tail = y\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        event=[]\n",
    "        for i in schedule:\n",
    "            for each in i:\n",
    "                event.append([each.start,each.end])\n",
    "        event.sort()\n",
    "        #合并区间\n",
    "        res=[event[0]]\n",
    "        l=1\n",
    "        while l<len(event):\n",
    "            while event[l][0]<res[-1][-1]:\n",
    "                res[-1][-1]=max(event[l][-1],res[-1][-1])\n",
    "                l+=1\n",
    "                if l==len(event):\n",
    "                    break\n",
    "            else:\n",
    "                    res.append(event[l])\n",
    "                    l+=1\n",
    "        result=[]\n",
    "        for i in range(len(res)-1):\n",
    "            if res[i][-1]!=res[i+1][0]:#排除把单点算进去的情况\n",
    "                result.append(Interval(res[i][-1],res[i+1][0]))\n",
    "            else:\n",
    "                continue\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        events = []\n",
    "        for emp in schedule:\n",
    "            for i in emp:\n",
    "                events.append([i.start, 1])\n",
    "                events.append([i.end, -1])\n",
    "        events.sort()\n",
    "\n",
    "        cnt = 0\n",
    "        prev = None\n",
    "        ans = []\n",
    "        for t, label in events:\n",
    "            if cnt==0 and prev and t>prev:\n",
    "                ans.append(Interval(prev, t))\n",
    "\n",
    "            cnt += label\n",
    "            prev = t\n",
    "\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    # 扫描线\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        OPEN, CLOSE = 0, 1\n",
    "\n",
    "        events = []\n",
    "        for emp in schedule:\n",
    "            for iv in emp:\n",
    "                events.append((iv.start, OPEN))\n",
    "                events.append((iv.end, CLOSE))\n",
    "\n",
    "        events.sort()\n",
    "        ans = []\n",
    "        prev = None\n",
    "        bal = 0\n",
    "        for t, cmd in events:\n",
    "            if bal == 0 and prev is not None:\n",
    "                ans.append(Interval(prev, t))\n",
    "\n",
    "            bal += 1 if cmd is OPEN else -1\n",
    "            prev = t\n",
    "\n",
    "        return ans\n",
    "\n",
    "    # 优先队列\n",
    "    def employeeFreeTime2(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        ans = []\n",
    "        pq = [(emp[0].start, ei, 0) for ei, emp in enumerate(avails)]\n",
    "        heapq.heapify(pq)\n",
    "        anchor = min(iv.start for emp in avails for iv in emp)\n",
    "        while pq:\n",
    "            t, e_id, e_jx = heapq.heappop(pq)\n",
    "            if anchor < t:\n",
    "                ans.append(Interval(anchor, t))\n",
    "            anchor = max(anchor, avails[e_id][e_jx].end)\n",
    "            if e_jx + 1 < len(avails[e_id]):\n",
    "                heapq.heappush(pq, (avails[e_id][e_jx+1].start, e_id, e_jx+1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        OPEN,CLOSE,events=0,1,[]\n",
    "        for emp in schedule:\n",
    "            for iv in emp:\n",
    "                events.append((iv.start,OPEN))\n",
    "                events.append((iv.end,CLOSE))\n",
    "        events.sort()\n",
    "\n",
    "        ret=[]\n",
    "        pre=None\n",
    "        bal=0\n",
    "        for t,cmd in events:\n",
    "            if bal==0 and pre is not None:\n",
    "                ret.append(Interval(pre,t))\n",
    "            bal+=1 if cmd is OPEN else -1\n",
    "            pre=t\n",
    "        return ret\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        cur = []\n",
    "        for p in schedule:\n",
    "            for ele in p:\n",
    "                cur.append([ele.start, ele.end])\n",
    "        cur.sort()\n",
    "        st, end = cur[0]\n",
    "        n = len(cur)\n",
    "        ans = []\n",
    "        for i in range(1, n):\n",
    "            t1, t2 = cur[i]\n",
    "            # 如果此区间终点小于end直接跳过即可\n",
    "            if t2 <= end:\n",
    "                continue\n",
    "            if t1 <= end:\n",
    "                end = t2\n",
    "            else:\n",
    "                ans.append([st, end])\n",
    "                st, end = cur[i]\n",
    "        ans.append([st, end])\n",
    "        res = []\n",
    "        for i in range(1, len(ans)):\n",
    "            res.append(Interval(ans[i-1][1], ans[i][0]))\n",
    "            \n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        hash_map = defaultdict(int)\n",
    "        for p in schedule:\n",
    "            for inter in p:\n",
    "                hash_map[inter.start] += 1\n",
    "                hash_map[inter.end] -= 1\n",
    "        keys = sorted(hash_map.keys())\n",
    "        \n",
    "        res = []\n",
    "        prev = None\n",
    "        cur_sum = 0\n",
    "        for now in keys:\n",
    "            if cur_sum == 0 and prev:\n",
    "                res.append(Interval(prev, now))\n",
    "            cur_sum += hash_map[now]\n",
    "            prev = now\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        intervals=[]\n",
    "        for a in schedule:\n",
    "            for b in a:\n",
    "                intervals.append([b.start,b.end])\n",
    "        intervals.sort()\n",
    "        #区间合并\n",
    "        n=len(intervals)\n",
    "        res=[intervals[0]]\n",
    "        for i in range(1,n):\n",
    "            if intervals[i][0]>=res[-1][1]:\n",
    "                res.append(intervals[i])\n",
    "            else:\n",
    "                res[-1][1]=max(res[-1][1],intervals[i][1])\n",
    "        ans=[]\n",
    "        for i in range(1,len(res)):\n",
    "            if res[i-1][1]<res[i][0]:\n",
    "                ans.append(Interval(res[i-1][1],res[i][0]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        a = []\n",
    "        for intervals in schedule:\n",
    "            for interval in intervals:\n",
    "                a.append(interval)        \n",
    "        a.sort(key=lambda x: (x.start, -x.end))\n",
    "        r = inf\n",
    "        ret = []\n",
    "        for interval in a:\n",
    "            if interval.start > r:\n",
    "                ret.append(Interval(r, interval.start))\n",
    "            # l = interval.start\n",
    "            r = max(r, interval.end) if r != inf else interval.end\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        events = list()\n",
    "        for employee in schedule:\n",
    "            for interval in employee:\n",
    "                events.append((interval.start, 1))\n",
    "                events.append((interval.end, -1))\n",
    "\n",
    "        events.sort(key = lambda x : (x[0], -x[1]))\n",
    "\n",
    "        results = list()\n",
    "        last = None\n",
    "        balance = 0\n",
    "        for _time, state in events:\n",
    "            if balance == 0 and last:\n",
    "                results.append(Interval(last, _time))\n",
    "\n",
    "            if state == 1:\n",
    "                balance += 1\n",
    "            else:\n",
    "                balance -= 1\n",
    "\n",
    "            last = _time\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "        \"\"\"\n",
    "        [1,2] [1,3] [4,10] [5,6]\n",
    "        [1,3] [4,10]\n",
    "        [1,3] [2,4] [2,5] [6,7] [9,12]\n",
    "        [1,5] [6,7] [9,12]\n",
    "        \"\"\"\n",
    "        nums = []\n",
    "        for x in schedule:\n",
    "            for val in x:\n",
    "                nums.append([val.start, val.end])\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        for x, y in nums:\n",
    "            if len(res) == 0 or res[-1][1] < x:\n",
    "                res.append([x, y])\n",
    "            else:\n",
    "                res[-1][1] = max(res[-1][1], y)\n",
    "        ans = []\n",
    "        print(nums)\n",
    "        print(res)\n",
    "        for i in range(1, len(res)):\n",
    "            x = res[i - 1][1]\n",
    "            y = res[i][0]\n",
    "            ans.append(Interval(x, y))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "def compare(self, other):\n",
    "    return self.end <= other.end\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "        working_time = []\n",
    "        heap = []\n",
    "\n",
    "        for i in range(len(schedule)):\n",
    "            employee = schedule[i]\n",
    "            n = len(employee)\n",
    "            heapq.heappush(heap, (employee[0].start, employee[0].end, i, 0, n))\n",
    "        \n",
    "        while heap:\n",
    "            info = heapq.heappop(heap)\n",
    "            start = info[0]\n",
    "            end = info[1]\n",
    "            i = info[2]\n",
    "            ind = info[3]\n",
    "            n = info[4]\n",
    "\n",
    "            if not working_time or working_time[-1][1] < start:\n",
    "                working_time.append((start, end))\n",
    "            \n",
    "            else:\n",
    "                prev = working_time.pop()\n",
    "                working_time.append((prev[0], max(prev[1], end)))\n",
    "            \n",
    "            if ind < n - 1:\n",
    "                new_employee = schedule[i][ind+1]\n",
    "                heapq.heappush(heap, (new_employee.start, new_employee.end, i, ind+1, n))\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        i = 0\n",
    "        n = len(working_time)\n",
    "        for i in range(1, n):\n",
    "            ans.append(Interval(working_time[i-1][1], working_time[i][0]))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "def compare(self, other):\n",
    "    return self.end <= other.end\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "        working_time = []\n",
    "        heap = []\n",
    "\n",
    "        for i in range(len(schedule)):\n",
    "            employee = schedule[i]\n",
    "            n = len(employee)\n",
    "            heapq.heappush(heap, (employee[0].start, employee[0].end, i, 0, n))\n",
    "        \n",
    "        while heap:\n",
    "            info = heapq.heappop(heap)\n",
    "            start = info[0]\n",
    "            end = info[1]\n",
    "            i = info[2]\n",
    "            ind = info[3]\n",
    "            n = info[4]\n",
    "\n",
    "            if not working_time or working_time[-1][1] < start:\n",
    "                working_time.append((start, end))\n",
    "            \n",
    "            else:\n",
    "                prev = working_time.pop()\n",
    "                working_time.append((prev[0], max(prev[1], end)))\n",
    "            \n",
    "            if ind < n - 1:\n",
    "                new_employee = schedule[i][ind+1]\n",
    "                heapq.heappush(heap, (new_employee.start, new_employee.end, i, ind+1, n))\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        i = 0\n",
    "        n = len(working_time)\n",
    "        for i in range(1, n):\n",
    "            ans.append(Interval(working_time[i-1][1], working_time[i][0]))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "        def inter(block1,block2):\n",
    "            l1,r1 = block1\n",
    "            l2,r2 = block2 \n",
    "            a,b = max(l1,l2),min(r1,r2)\n",
    "            if a>= b:return None\n",
    "            return [a,b]\n",
    "\n",
    "\n",
    "        def interSection(sch1,sch2):\n",
    "            idx1 ,idx2 = 0,0\n",
    "            res = []\n",
    "            while idx1<len(sch1) and idx2<len(sch2):\n",
    "                ret = inter(sch1[idx1] ,sch2[idx2])\n",
    "                if ret :\n",
    "                    res.append(ret)\n",
    "                if sch1[idx1][1] < sch2[idx2][1] :#右边更小的前进\n",
    "                    idx1 += 1\n",
    "                else:\n",
    "                    idx2 += 1\n",
    "            return res \n",
    "        \n",
    "        sches = []\n",
    "        INF = 10**9\n",
    "        for sch in schedule:\n",
    "            tmp = [(-INF, sch[0].start  )] \n",
    "            for i in range(len(sch)-1):\n",
    "                tmp.append( ( sch[i].end  , sch[i+1].start   ) )\n",
    "            tmp .append( ( sch[-1].end , INF  ) ) \n",
    "            sches.append(tmp)\n",
    "        #print(sches)\n",
    "        ans = sches[0]\n",
    "        for i in range( 1, len(sches) ):\n",
    "            ans = interSection(ans,sches[i])\n",
    "\n",
    "        return [ Interval(a,b) for a,b in ans[1:-1] ]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for an Interval.\n",
    "class Interval:\n",
    "    def __init__(self, start: int = None, end: int = None):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\"\"\"\n",
    "def compare(self, other):\n",
    "    return self.end <= other.end\n",
    "\n",
    "class Solution:\n",
    "    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':\n",
    "\n",
    "        working_time = []\n",
    "        heap = []\n",
    "\n",
    "        for i in range(len(schedule)):\n",
    "            employee = schedule[i]\n",
    "            n = len(employee)\n",
    "            heapq.heappush(heap, (employee[0].start, employee[0].end, i, 0, n))\n",
    "        \n",
    "        while heap:\n",
    "            info = heapq.heappop(heap)\n",
    "            start = info[0]\n",
    "            end = info[1]\n",
    "            i = info[2]\n",
    "            ind = info[3]\n",
    "            n = info[4]\n",
    "\n",
    "            if not working_time or working_time[-1][1] < start:\n",
    "                working_time.append((start, end))\n",
    "            \n",
    "            else:\n",
    "                prev = working_time.pop()\n",
    "                working_time.append((prev[0], max(prev[1], end)))\n",
    "            \n",
    "            if ind < n - 1:\n",
    "                new_employee = schedule[i][ind+1]\n",
    "                heapq.heappush(heap, (new_employee.start, new_employee.end, i, ind+1, n))\n",
    "        \n",
    "        print(working_time)\n",
    "        ans = []\n",
    "\n",
    "        i = 0\n",
    "        n = len(working_time)\n",
    "        for i in range(1, n):\n",
    "            ans.append(Interval(working_time[i-1][1], working_time[i][0]))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
